package tree;

class SolutionTwo {
    int n = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length != inorder.length || preorder.length <= 0 || inorder.length <= 0){
            return null;
        }
        return helper(preorder,inorder,0,inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int[] inorder,int left,int right){
        if(left > right){
            return null;
        }
        int aim = preorder[n];
        n++;
        int index = findIndex(aim,inorder);
        TreeNode root = new TreeNode(aim);
        root.left = helper(preorder,inorder,left,index-1);
        root.right = helper(preorder,inorder,index+1,right);
        return root;
    }

    private int findIndex(int aim,int[] inorder){
        for(int i = 0; i < inorder.length; i++){
            if(aim == inorder[i]){
                return i;
            }
        }

        return -1;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}